//括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。 
//
// 说明：解集不能包含重复的子集。 
//
// 示例： 
//
// 
//输入：n = 3
//输出：
//[
//  "((()))",
//  "(()())",
//  "(())()",
//  "()(())",
//  "()()()"
//]
// 
//
// Related Topics 字符串 动态规划 回溯 👍 144 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-08-31 15:28:54
 * @description 面试题 08.09.括号
 */
public class BracketLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 BracketLcci fun=new BracketLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //栈/递归/回溯
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
		backTrack(res,new StringBuilder(),0,0,n);
		return res;
    }
	private void  backTrack(List<String> res,StringBuilder track,int left,int right,int n) {
		if (track.length() == 2 * n) {
			res.add(track.toString());
			return;
		}
		if (left < n) {
			track.append('(');
			backTrack(res, track, left + 1, right, n);
			track.deleteCharAt(track.length() - 1);
		}
		if (right < left) {
			track.append(')');
			backTrack(res, track, left, right + 1, n);
			track.deleteCharAt(track.length() - 1);
		}
	}
	// 每个括号都可以用(a）b的形式表示，a和b都是合法的括号组合
	// 其中a有0~n-1对括号，b有n-1~0对括号
	// 递归+记忆化搜索
	ArrayList[] cache = new ArrayList[100];

	public List<String> generate(int n) {
		if (cache[n] != null) {
			return cache[n];
		}
		ArrayList<String> ans = new ArrayList<String>();
		if (n == 0) {
			ans.add("");
		} else {
			for (int c = 0; c < n; ++c) {
				// c表示a的括号对数
				for (String left: generate(c)) {
					// n-1-c表示b的括号对数
					for (String right: generate(n - 1 - c)) {
						ans.add("(" + left + ")" + right);
					}
				}
			}
		}
		cache[n] = ans;
		return ans;
	}

	public List<String> generateParenthesis1(int n) {
		return generate(n);
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
